package year2023.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code01_CoverMax {


    //最大线段重合问题
    /*给定很多线段，每个线段都有两个数组[start,end]
      表示线段开始位置和结束位置，左右都是闭区间
      规定：
      1) 线段的开始和结束位置一定都是整数
      2) 线段重合区域的长度必须 >=1
      返回线段最多重合区域中，包含了几条线段
    * */
    public static class Line{
        public int start;
        public int end;
        public Line(int s, int e){
            start = s;
            end = e;
        }
    }

    public static class StartComparator implements Comparator<Line>{

        @Override
        public int compare(Line o1, Line o2){
            return o1.start - o2.start;
        }
    }

    public static class EndComparator implements Comparator<Line> {

        @Override
        public int compare(Line o1, Line o2){
            return o1.end - o2.end;
        }
    }

    //枚举
    public static int maxCover1(int[][] lines){
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < lines.length; i++) {
            min = Math.min(min,lines[i][0]);
            max = Math.max(max,lines[i][1]);
        }
        int cover = 0;
        for (double p = min + 0.5; p < max; p++){
            int cur = 0;
            for (int i = 0; i < lines.length; i++) {
                if (lines[i][0] < p && lines[i][1] > p){
                    cur++;
                }
            }
            cover = Math.max(cover,cur);
        }
        return cover;
    }

    public static int maxCover2(int[][] m){
        Line[] lines = new Line[m.length];
        for (int i = 0; i < m.length; i++) {
            lines[i] = new Line(m[i][0],m[i][1]);
        }
        Arrays.sort(lines,new StartComparator());
        //lines
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int max = 0;
        for (int i = 0; i < lines.length; i++) {
            // lines[i] -> cur 在黑盒中 把 >=cur.start 的东西都弹出来
            while (!heap.isEmpty() && heap.peek() <= lines[i].start){
                heap.poll();
            }
            heap.add(lines[i].end);
            max = Math.max(max, heap.size());
        }
        return max;
    }



}
